package 动态规划.dp声明正序And倒序;

import java.util.Scanner;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/5/26 14:50
 */
public class 洛谷p2473奖励关 {
    /*
       oi 题, 大神 李煜东 , 说的这种 ,dp 倒推 和正推!

       所以考虑从已知推未知，采用倒推，可以推出每一个可能的状态。
       主要的问题是 ,有些 位置点 按照某种顺序 ,是 无法判断可达 不可达!

       ==
       注意看下 题解区的 别人的看法!
       https://www.luogu.com.cn/problem/solution/P2473
     */

    public double solution() {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt(), n = sc.nextInt();
        int rewards[][] = new int[n + 1][2];

        for (int i = 1; i <= n; i++) {
            int state = 0;
            rewards[i][0] = sc.nextInt();
            int in;
            while ((in = sc.nextInt()) != 0) {
                state |= 1 << (in - 1);
            }
            rewards[i][1] = state;
        }
        Double dp[][] = new Double[k + 1][1 << n];
        return recursion(0,0,rewards,k,dp);
//        return recursion(k,0,rewards,dp);
    }

    public double recursion(int index, int state, int rewards[][],int k,Double dp[][]) {
        // basecase   up to  the end
         if(index == k){
             // return  a value  which can not impact the result
             return 0.0;
         }
         if(dp[index][state] != null){
             return dp[index][state];
         }

        double ans = 0.0;
        for (int i = 1; i < rewards.length; i++) {
            // 判断此时 能不能 选择 i号 奖品，（有选择的前置条件）
            if ((state & rewards[i][1]) != rewards[i][1]) { // 说明没有达到 该奖品前置条件， 该次奖励 白白浪费 , 没有奖励， 只能 白白的进入下一层 抛奖励
//                ans += recursion(index + 1, state | (1 << index - 1), rewards,k);
                ans += recursion(index + 1, state, rewards,k,dp);
            } else {
                // 这里的体现是： 如果 当前的 抛出的奖品的前置 条件满足的话， 可以有两种选择， 手下该奖品， 或者不要
                ans += Math.max(recursion(index + 1,state | (1 << i - 1),rewards,k,dp) + rewards[i][0],recursion(index + 1,state,rewards,k,dp));
            }
        }

        return dp[index][state] = ans / (rewards.length - 1);
    }

    /*
    这怎么感觉 折磨 绕啊！
    正着 推 是错误的！
     */
    public double solutionOne(){
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt(), n = sc.nextInt();
        int rewards[][] = new int[n + 1][2];

        for (int i = 1; i <= n; i++) {
            int state = 0;
            rewards[i][0] = sc.nextInt();
            int in;
            while ((in = sc.nextInt()) != 0) {
                state |= 1 << (in - 1);
            }
            rewards[i][1] = state;
        }
        Double dp[][] = new Double[k + 1][1 << n];
        // 这里还需不需要进行一个初始化呢

        return recursion(k,0,rewards,dp);
    }

    public double recursion(int index,int state,int rewards[][],Double dp[][]){
        if(index == 0) {
            return 0.0;
        }
        if(dp[index][state] != null){
            return dp[index][state];
        }
        double ans = 0.0;
        for(int i = 1;i < rewards.length;i++){
            if((state & rewards[i][1]) != rewards[i][1]){
                ans += recursion(index - 1,state,rewards,dp);
            }else{
                ans += Math.max(recursion(index - 1,state,rewards,dp),recursion(index - 1,state | (1 << i - 1),rewards,dp) + rewards[i][1]);
            }
        }
        return dp[index][state] = ans / (rewards.length - 1);
    }

    public double recursion(int index,int state,int rewards[][]){
        if(index == 0) {
            return 0.0;
        }
        double ans = 0.0;
        for(int i = 1;i < rewards.length;i++){
            if((state & rewards[i][1]) != rewards[i][1]){
                ans += recursion(index - 1,state,rewards);
            }else{
                ans += Math.max(recursion(index - 1,state,rewards),recursion(index - 1,state | (1 << i - 1),rewards) + rewards[i][1]);
            }
        }
        return ans / (rewards.length - 1);
    }



    public static void main(String[] args) {
        double solution = new 洛谷p2473奖励关().solution();
        System.out.println(solution);
        System.out.printf("%6f",solution);

//        double ans = new 洛谷p2473奖励关().solutionOne();
//
//        System.out.printf("%6f",ans);
    }

}
